package woa.queue;

import java.util.*;

/**
 * 完全平方数问题
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方
 * 数，而 3 和 11 不是。
 *
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 *
 * @author wangpeng
 * @date 2021/11/26
 */
public class NumSquaresProblem {

    public static int numSquares(int n) {
        Set<Integer> cache = new HashSet<>();
        int count = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int sum = queue.poll();
                if (sum == n) {
                    return count;
                }
                int j = 1;
                int k = sum + 1;
                while (k <= n) {
                    if (!cache.contains(k)) {
                        queue.add(k);
                        cache.add(k);
                    }
                    j++;
                    k = sum + j * j;
                }
            }

            count++;
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(numSquares(15));
    }
}
